package zuo.baseUP2_Sorted_UnionField;

import java.lang.annotation.ElementType;
import java.util.Arrays;
import java.util.concurrent.ConcurrentLinkedQueue;

/**
 * @Author: Forx
 * @Data: 2021/6/17
 * @Desc: Algorithm - zuo.baseUP2_Sorted_UnionField
 * @Version: v1.0
 */
public class Main {
    /**
     *
     * 岛问题
     * [题目]
     * 个矩阵中只有0和1两种值,每个位置都可以和自己的上、下、左、右四个位置相连,如
     * 果有一片1连在一起,这个部分叫做一个岛,求一个矩阵中有多少个岛?
     * [举例]
     * 001010
     * 111010
     * 100100
     * 000000
     * 这个矩阵中有三个岛
     * [进阶]
     * 如何设计一个并行算法解决这个问题
     *
     * 遍历,每遇到一个1看看他周围有没有岛,有的话就加入,没有的话就是一个独立的岛
     *
     * */
    public static boolean fillIsland(int[][] map,int row,int col){
        while (map[row-1][col]==1 || map[row+1][col]==1 || map[row][col-1]==1 || map[row][col+1]==1){
            if(map[row-1][col]==1 ){
                map[row-1][col]=2;
                fillIsland(map,row-1,col);

            }else if(map[row+1][col]==1 ){
                map[row+1][col]=2;
                fillIsland(map,row+1,col);

            }else if(map[row][col-1]==1){
                map[row][col-1]=2;
                fillIsland(map,row,col-1);
            }else{
                map[row][col+1]=2;
                fillIsland(map,row,col+1);
            }
        }
        return true;
    }

    public static void fillIsland2(int[][] map,int row,int col,int w,int h){
        if(row<0 || col<0|| row >= h || col >= w || map[row][col]!=1){
            return;
        }
        map[row][col]=0;
        printBuff(map);
        try {
            Thread.sleep(10);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        clearBuff(map);
        fillIsland2(map,row-1,col,w,h);
        fillIsland2(map,row+1,col,w,h);
        fillIsland2(map,row,col-1,w,h);
        fillIsland2(map,row,col+1,w,h);
    }

    public static int islandNum(int[][] map){


        //int num = 0;
        int w = map[0].length;
        int h = map.length;
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                if(map[i][j]==1){
                    fillIsland2(map,i,j,w,h);
                }
            }
        }
        return 0;
    }
    public static void printBuff(int[][] map){
        for (int i = 0; i < map.length; i++) {
            System.out.println(Arrays.toString(map[i]));
        }
    }
    public static void clearBuff(int[][] map){
        for (int i = 0; i <2; i++) {
            System.out.println();
        }
    }

    /**
     *
     * 并查集 看unionfind文件
     *
     * 并行解法:
     * 并查集
     *
     * */



    public static void main(String[] args) {
        int[][] map = {
                {1,1,0,0,0,0,0},
                {0,1,0,1,0,1,0},
                {0,1,1,1,0,1,0},
                {0,1,0,1,1,0,0},
                {0,0,0,0,0,0,0},
        };
        System.out.println(islandNum(map));



    }


}
